package com.zjsru.plan2024.oneday;

import java.util.HashMap;
import java.util.Map;

/**
 * 575. 分糖果
 * @Author: cookLee
 * @Date: 2024-06-02
 */
public class DistributeCandies {

    /**
     * 主
     * \
     * 输入：candyType = [1,1,2,2,3,3]
     * 输出：3
     * 解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。
     * \
     * 输入：candyType = [1,1,2,3]
     * 输出：2
     * 解释：Alice 只能吃 4 / 2 = 2 枚糖，不管她选择吃的种类是 [1,2]、[1,3] 还是 [2,3]，她只能吃到两种不同类的糖。
     * \
     * 输入：candyType = [6,6,6,6]
     * 输出：1
     * 解释：Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        DistributeCandies distributeCandies = new DistributeCandies();
        int[] candyType = new int[]{1,1,2,2,3,3};
        System.out.println(distributeCandies.distributeCandies(candyType));
    }

    /**
     * 分发糖果
     *
     * @param candyType 糖果类型
     * @return int
     */
    public int distributeCandies(int[] candyType) {
        //获取最大可食用数量,数组长度永远是偶数
        int max = candyType.length / 2;
        Map<Integer, Integer> count = new HashMap<>();
        for (int one : candyType) {
            count.put(one, count.getOrDefault(one, 0) + 1);
        }
        return Math.min(count.size(), max);
    }

    /**
     * 分发候选人2,优化查询耗时
     *
     * @param candyType 糖果类型
     * @return int
     */
    public int distributeCandies2(int[] candyType) {
        int len = candyType.length;
        byte[] set = new byte[200001];
        int count = 0;
        for (int i = 0; i < len; i++) {
            //找出未被记录的数字
            count += 1 - set[10000 + i];
            if (count == candyType.length / 2) {
                return count;
            }
            //代表已经查询过
            set[10000 + i] = 1;
        }
        return count;
    }

}
